<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
<head>
  <meta http-equiv="Content-Type" content="text/html; charset=utf-8"/>
  <title>SIMILE | Gadget | Design Principles</title>
  <link rel="stylesheet" href="http://simile.mit.edu/styles/default.css" type="text/css"/>
  <style>
     #body {
        margin-bottom: 220px;
     }
    </style>
</head>
<body>
<!--#include virtual="sidebar.html" -->
<ul id="path">
  <li><a href="http://simile.mit.edu/" title="Home">SIMILE</a></li>
  <li><a href="http://simile.mit.edu/gadget/" title="Home">Gadget</a></li>
  <li><span>Design Principles</span></li>
</ul>
<div id="body">
<h1>Design Principles</h1>

<p>The <a href="http://www.w3.org/TR/REC-xml/">XML Specification</a> describes 
both a syntax and a model. The syntax is based on angle
brakets, while the model is basically a tree of nodes, which could be
either elements, attributes or text containers. 
The <a href="http://www.w3.org/TR/xml-infoset/">XML Infoset
Specification</a> describes the XML data model in detail.</p>

<p>The 'names' of those nodes are not dictated by the XML model or
syntax (XML is, in fact, a metalanguage, a language to describe languages)
and, in general, there is no reason why nodes with the same name
or content should be reused throughout the same XML tree, but in real life
the number of different 'names' for those nodes is very small compared to
the amount of data that the XML tree contains. In practice, the amount of
different 'names' is a function of the different namespaces used by the
XML tree and not a function of the size of the XML tree itself.</p>

<p>This is the basic property upon which XML inspection starts to make
sense: when the complexity of the structural patterns exhibited by the
XML dataset is not a function of the size of the dataset. One example
for all: the web contains billions of documents, and it is possible to
convert all of them into XHTML and create a huge XML dataset several
TeraBytes big. But the structural complexity of that XML dataset would
not be a function of its size, but a function of the schemas used,
mainly XHTML.</p>

<p>An example of a dataset that doesn't exhibit this property would be
a dataset assembled taking a single document as an example of an
instance from collection of schemas, but even in that case, real life
usage of XML shows that the number of schemas grows a lot slower 
than the amount of XML data generated.</p>

<p>Another interesting property that real life XML datasets exhibit is
the fact that 'semantic' information (information that shows the user
how to understand this) is not encoded in the node name but in the
entire sequence of names that leads to that node. In brevity, in its
XPath. An example of this is the use of the node "email" that has no
meaning by itself, if not indicating that it contains an email address,
but the path fragment "person/email" will indicate that the "email"
node is contained inside the "person" node and for that reason, is
associated to that.</p>

<p>Real life analysis shows that the number of XPaths is a function of
the complexity of the schema, therefore, again, not a function of the
complexity of the dataset.</p>

<h2><a name="inspection"></a>XML Inspection</h2>
<p>The process of XML inspection is based on the following assumptions:</p>
<ul>
  <li>the data is encoded in literals, either as textual nodes inside
elements or as attribute values</li>
  <li>the metadata is encoded in the XPaths that identify those literals</li>
  <li>mixed content is considered as data</li>
</ul>

<p>Given those assumptions, which stem from the fact that big datasets
are normally encoding databases and therefore mixed content is rare or
used as part of descriptions, we would like to "inspect" the dataset to
have an overview of how it looks like and normally this means answering
the following questions:</p>
<ul>
  <li>what xpaths were used in this dataset?</li>
  <li>how many times were they used?</li>
</ul>

<p>Another property that real life XML datasets exhibit is not only the
high reusability of nodes and, in general, xpaths, but also the level
of reusability of the literals contained in those paths. As an example,
a path like "object/@id" will probably have a different literal
associated to it for each use, while a path like "song/genre" will
probably exhibit a higher reusability of the literals.</p>

<h2><a name="how_it_works"></a>How Gadget Works</h2>
<p>The key in dealing with large quantities of data is to process them
as stream and store the results, rather than attemp to store all data
in memory and process it from there. Obviously, this is good in theory,
but in practice one must retain state about what happened before in
order, for example, to be able to identify if a literal was found
previously in the document, without having to scan the document
everytime.</p>

<p>Gadget works as a SAX event handler and consumes the SAX events generated
by the XML parser. These SAX events are used to generate a minimal tree
representation in memory of all the xpaths that were found.</p>

<p>Gadget creates a different b-tree index on disk for each different xpath that it finds, 
plus another summary index that keeps a list of all the xpath found and their
collective value. The collection all the xpath found is used to emerge a tree which
is then shown by the web application as a condensed summary of the XML dataset.</p>

<p>The indexer is also responsible for generating the sparklines and the distribution
charts since they don't change.</p>

<h2><a name="how_value_clustering_works"></a>How Value Clustering Works</h2>
<p>Gadget performs a primitive yet very scalable solution to find values in the same path
that might be variations of the same concept or name. This is meant to be a guide for
the data maintainers to find variants that might be considered noisy and misleading
to users, especially when dealing with faceted browsing.</p>
<p>Clustering is performed by hashing collisions: each value is pruned and normalized
and a key is extracted out of the value, when two different values generate the
same key, they belong to the same cluster.</p>
<p>This simple yet very effective algorithm allows us to:</p>
<ul>
 <li>Reuse the existing b-tree infrastructure used to store the other persistent maps</li>
 <li>Scale linearely with the amount of data to be processed because each key-generation
 is independent of the other values</li>
</ul>
<p>The key generation algorithm performs the following steps:</p>
<ul>
 <li>spaces are removed from the front and back of the value</li>
 <li>the value is transformed into its lowercase counterpart</li>
 <li>all punctuation is removed</li>
 <li>non-identifying tokens (mrs, mr, dr, miss...) are removed</li>
 <li>single char tokens are removed</li>
 <li>isolated digits are removed</li>
 <li>the remaining value is tokenized by spaces then:
  <ul>
    <li>the tokens ordered alphanumerically</li>
    <li>the tokens are appended into one string</li>
  </ul>
 </li>
</ul>
<p>The resulting string is the cluster key.</p>
<p class="note">The above algorithm works best for names and it is, by no means, 
supposed to be a general purpose algorithm for text clustering. We plan to spend
more research and implementation effort in this space in the future.</p>
</div>
<!--#include virtual="../footer.html" -->
</body>
</html>
